//给你一个整数数组 nums 和一个整数 k。 
//
// 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。 
//
// 请返回这个数组中「优美子数组」的数目。 
//
// 
//
// 示例 1： 
//
// 输入：nums = [1,1,2,1,1], k = 3
//输出：2
//解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
// 
//
// 示例 2： 
//
// 输入：nums = [2,4,6], k = 1
//输出：0
//解释：数列中不包含任何奇数，所以不存在优美子数组。
// 
//
// 示例 3： 
//
// 输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
//输出：16
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 50000 
// 1 <= nums[i] <= 10^5 
// 1 <= k <= nums.length 
// 
// Related Topics 数组 哈希表 数学 滑动窗口 
// 👍 188 👎 0

  
package com.zwy.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zwy 
 */
public class CountNumberOfNiceSubarrays{
    public static void main(String[] args) {
        Solution solution = new CountNumberOfNiceSubarrays().new Solution();
        int []nums = {2,2,2,1,2,2,1,2,2,2};
        int k = 2;
        solution.numberOfSubarrays(nums,k);
      }
     
/**
 *时间复杂度为:
 * @author zwy 
 */ 
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        // 滑窗
        int res=0,count=0;
        int left=0,right=0;
        int tmp=0;
        while (right<nums.length){
            if (count<k){
                count+=nums[right]&1;
                right++;
            }
            if (count==k){
                tmp=0;
                while (count==k){
                    ++res;++tmp;
                    count-=nums[left]&1;
                    ++left;
                }
            }else res+=tmp;
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}